package class23;

import class11.TopologySort;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class LongestSumSubArrayLengthInPositiveArray2 {

    public static int getMaxLength(int[] arr,int K){
        if (arr == null || arr.length == 0|| K <=0){
            return 0;
        }
        int L = 0;
        int R = 0;
        int wsum = arr[0];
        int len = 0;
        while (R <arr.length){
            if (wsum == K){
                len = Math.max(len,R-L+1);
                wsum -=arr[L++];
            }else if (wsum < K){
                R++;
                if (R == arr.length)
                    break;
                wsum += arr[R];
            }else {
                wsum -= arr[L++];
            }
        }
        return len;
    }

    public static int right(int[] arr,int K){
        int max = 0;
        for (int i=0;i<arr.length;i++){
            for (int j=0;j<arr.length;j++){
                if (valid(arr,i,j,K)){
                    max = Math.max(max,j-i+1);
                }
            }
        }
        return max;
    }

    public static boolean valid(int[] arr,int L,int R,int K){
        int sum = 0;
        for (int i = L;i<=R;i++){
            sum += arr[i];
        }
        return sum == K;
    }

    public static int[] generatePositiveArray(int size,int value){
        int[] ans = new int[size];
        for (int i= 0;i!=size;i++){
            ans[i]=(int)(Math.random()*value)+1;
        }
        return ans;
    }

    public static void printArray(int[] arr){
        for (int i = 0;i != arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 500000;
        System.out.println("test begin!");
        for (int i = 0;i< testTime;i++){
            int[] arr = generatePositiveArray(len,value);
            int K = (int)(Math.random()*value)+1;
            int ans1 = getMaxLength(arr,K);
            int ans2 = right(arr,K);
            if (ans1 != ans2){
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("test finish!");
    }
}
